Inwersje kontraatakują
To zadanie pochodzi z Kółka Informatycznego w Staszicu.
Napisz program, który dla danego ciągu obliczy liczbę jego inwersji.
Inwersją nazywamy taką parę (niekoniecznie kolejnych) indeksów (i,j), że i<j,
ale ai>aj.
Na przykład ciąg (1,3,4,2) ma 2 inwersje: (3,2) oraz (4,2).
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia ciąg liczb całkowitych,
- obliczy liczbę jej inwersji,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita n,
(1 <=n<= 60000), oznaczająca liczbę elementów ciągu. Kolejnych
n wierszy zawiera po jednej liczbie całkowitej ai
(-109 <= ai<= 109).
Wyjście
W pierwszym i jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą, oznaczającą
liczbę inwersji w podanym ciągu.
Przykład
Dla danych wejściowych:
4
1
3
4
2
Poprawnym wynikiem jest:
2
English